/*
 * @lc app=leetcode.cn id=994 lang=golang
 *
 * [994] 腐烂的橘子
 */

// @lc code=start

func orangesRotting(grid [][]int) int {
	var bfs func(i, j int)
	m, n := len(grid), len(grid[0])
	ans := -1

	check := func(i, j int) bool {
		return 0 <= i && i < m && 0 <= j && j < n
	}
	queue := NewQueue()
	dir := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	bfs = func(i, j int) {
		if !check(i, j) {
			return
		}
		if grid[i][j] >= 2 {
			for k := 0; k < 4; k++ {
				x, y := dir[k][0]+i, dir[k][1]+j
				if check(x, y) && grid[x][y] == 1 {
					grid[x][y] = 2 + grid[i][j] + 1
					queue.Push(x)
					queue.Push(y)
					ans = max(anx, grid[x][y]-2)
				}
			}
		}

	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, [2]int{i, j})
			}
		}
	}
	for len(queue) > 0 {
		for _, v := range queue {
			bfs(v[0], v[1])
		}
	}

	return ans
}

type que struct {
	data []int
	size int
}

func NewQueue() *que {
	return &que{
		data: []int{},
		size: 0,
	}
}
func (q *que) Push(v int) {
	q.data = append(q.data, v)
	q.size++
}
func (q *que) Pop() int {
	if q.size == 0 {
		return -1
	}
	v := q.data[0]
	q.data = q.data[1:]
	q.size--
	return v
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// @lc code=end

